๐Ÿ‘ฉโ€๐Ÿ’ป 1707. ์ด๋ถ„๊ทธ๋ž˜ํ”„

@Seongukbaek Posted January 12, 2022 ยท Updated January 12, 2022 ยท 7 min read

๋ฌธ์ œ

๊ทธ๋ž˜ํ”„์˜ ์ •์ ์˜ ์ง‘ํ•ฉ์„ ๋‘˜๋กœ ๋ถ„ํ• ํ•˜์—ฌ, ๊ฐ ์ง‘ํ•ฉ์— ์†ํ•œ ์ •์ ๋ผ๋ฆฌ๋Š” ์„œ๋กœ ์ธ์ ‘ํ•˜์ง€ ์•Š๋„๋ก ๋ถ„ํ• ํ•  ์ˆ˜ ์žˆ์„ ๋•Œ, ๊ทธ๋Ÿฌํ•œ ๊ทธ๋ž˜ํ”„๋ฅผ ํŠน๋ณ„ํžˆ ์ด๋ถ„ ๊ทธ๋ž˜ํ”„ (Bipartite Graph) ๋ผ ๋ถ€๋ฅธ๋‹ค.

๊ทธ๋ž˜ํ”„๊ฐ€ ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด ๊ทธ๋ž˜ํ”„๊ฐ€ ์ด๋ถ„ ๊ทธ๋ž˜ํ”„์ธ์ง€ ์•„๋‹Œ์ง€ ํŒ๋ณ„ํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

  • ์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋Š”๋ฐ, ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ K๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ์งธ ์ค„์—๋Š” ๊ทธ๋ž˜ํ”„์˜ ์ •์ ์˜ ๊ฐœ์ˆ˜ V์™€ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ E๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ์ •์ ์—๋Š” 1๋ถ€ํ„ฐ V๊นŒ์ง€ ์ฐจ๋ก€๋กœ ๋ฒˆํ˜ธ๊ฐ€ ๋ถ™์–ด ์žˆ๋‹ค. ์ด์–ด์„œ ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ E๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ๊ฐ„์„ ์— ๋Œ€ํ•œ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง€๋Š”๋ฐ, ๊ฐ ์ค„์— ์ธ์ ‘ํ•œ ๋‘ ์ •์ ์˜ ๋ฒˆํ˜ธ u, v (u โ‰  v)๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ

  • K๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ๊ทธ๋ž˜ํ”„๊ฐ€ ์ด๋ถ„ ๊ทธ๋ž˜ํ”„์ด๋ฉด YES, ์•„๋‹ˆ๋ฉด NO๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ“ Logic

class Graph { final List<Integer>[] graph; final int[] Binary = { -1, 1 }; int[] discovered; boolean isBinaryGraph = true; int toggle = 0; public Graph(int size) { this.graph = new ArrayList[size+1]; discovered = new int[size+1]; for (int i = 0; i <= size; i++) { graph[i] = new ArrayList<>(); } } }
  • ๊ทธ๋ž˜ํ”„์˜ ์ •๋ณด๋ฅผ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•œ ํด๋ž˜์Šค
public boolean solution() { for (int i=1; i < graph.length; i++) { if (graph[i].size() > 0 & discovered[i] == 0) { isBinaryGraph = this.bfs(i); if (!isBinaryGraph) break; } } return this.isBinaryGraph; }
  • ์ธ์ ‘ ์ •์  ์ •๋ณด๊ฐ€ ์žˆ๊ณ , ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ •์ ์— ๋Œ€ํ•ด BFS ๋ฅผ ์ˆ˜ํ–‰

    • ์ •์ ์˜ ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋Š” (0: ๋ฏธ๋ฐฉ๋ฌธ), (-1: 1๊ทธ๋ฃน), (1: 2๊ทธ๋ฃน)
  • ์ด๋ถ„ ๊ทธ๋ž˜ํ”„์ธ์ง€๋ฅผ ์ €์žฅํ•˜๋Š” isBinaryGraph ์— false ๊ฐ€ ๋‚˜์˜ค๋ฉด ๋” ์ด์ƒ์˜ ํƒ์ƒ‰์„ ์ข…๋ฃŒํ•˜๊ณ  ์ด๋ฅผ ๋ฐ˜ํ™˜
  • false ๊ฐ€ ๊ณ„์† ๋‚˜์˜ค์ง€ ์•Š์œผ๋ฉด ์ด๋ถ„ ๊ทธ๋ž˜ํ”„์ด๋ฏ€๋กœ ์ดˆ๊ธฐ๊ฐ’์ธ true ๊ฐ€ ๋ฐ˜ํ™˜
public boolean bfs(int parent) { Queue<Integer> q = new LinkedList<>(); q.add(parent); while (!q.isEmpty()) { int now = q.poll(); if (discovered[now] == 0) { discovered[now] = Binary[toggle]; } toggle = (discovered[now] == -1 ? 1 : 0); for (int tmp : graph[now]) { if (discovered[tmp] == 0) { q.add(tmp); discovered[tmp] = Binary[toggle]; } else if (discovered[tmp] == discovered[now]) return false; } } return true; }
  • Queue ๋ฅผ ์ด์šฉํ•˜์—ฌ BFS ์ˆ˜ํ–‰
  • ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ •์ ์€ ๋ฐฉ๋ฌธ ์—ฌ๋ถ€ ๊ฐ’์„ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” Binary ๋ฐฐ์—ด๊ณผ toggle ๋ณ€์ˆ˜๋กœ setting
  • BFS ๋‹จ๊ณ„๋ณ„ ์„œ๋กœ ๋‹ค๋ฅธ ๋ฐฉ๋ฌธ ๊ฐ’ ์ €์žฅ
  • ๋‹ค์Œ ๋ฐฉ๋ฌธํ•  ์ •์ ์ด ์ด๋ฏธ ๋ฐฉ๋ฌธํ–ˆ๊ณ , ํ˜„์žฌ ๋ฐฉ๋ฌธ ์ •์ ๊ณผ ๊ฐ™์€ ๋ฐฉ๋ฌธ ๊ฐ’์„ ๊ฐ€์ง„๋‹ค๋ฉด ์ด๋ถ„ ๊ทธ๋ž˜ํ”„ ๋ถˆ๊ฐ€

๐Ÿ“„ ํ‹€๋ฆฐ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.ArrayList; import java.util.Scanner; class Graph { private final ArrayList<ArrayList<Integer>> graph; private int[] discovered; private boolean oddCycle = false; private int dis; public Graph(int size) { this.graph = new ArrayList<>(); for (int i = 0; i <= size; i++) { graph.add(new ArrayList<>()); } } public void DoubleAdd(int x, int y) { graph.get(x).add(y); graph.get(y).add(x); } public boolean isOddCycle(int s, int n) { discovered = new int[20001]; dis = 1; this.dfs(s, n); return this.oddCycle; } public void dfs(int parent, int now) { discovered[now] = dis++; int size = graph.get(now).size(); if (size == 0) return; for (int i = 0; i < size; i++) { int idx = graph.get(now).get(i); if (discovered[idx] == 0) { this.dfs(now, idx); } else if (idx != parent && ((discovered[now] - discovered[idx])%2 == 0)) { this.oddCycle = true; } } } } public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); while (T > 0) { int v = sc.nextInt(); int e = sc.nextInt(); sc.nextLine(); boolean isOdd = false; Graph g = new Graph(v); for (int i = 0; i < e; i++) { String str = sc.nextLine(); int a = str.charAt(0) - '0'; int b = str.charAt(2) - '0'; g.DoubleAdd(a,b); } for (int i = 1; i <= v; i++) { isOdd = g.isOddCycle(i, i); // odd๊ฐ€ ํ•œ ๋ฒˆ์ด๋ผ๋„ true๋ฉด ์ด๋ถ„ ๊ทธ๋ž˜ํ”„๊ฐ€ ๋  ์ˆ˜ ์—†๋‹ค. if (isOdd) break; } if (!isOdd) System.out.println("YES"); else System.out.println("NO"); T-=1; } sc.close(); } }

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Graph { final List<Integer>[] graph; final int[] Binary = { -1, 1 }; int[] discovered; boolean isBinaryGraph = true; int toggle = 0; public Graph(int size) { this.graph = new ArrayList[size+1]; discovered = new int[size+1]; for (int i = 0; i <= size; i++) { graph[i] = new ArrayList<>(); } } public void DoubleAdd(int x, int y) { graph[x].add(y); graph[y].add(x); } public boolean solution() { for (int i=1; i < graph.length; i++) { if (graph[i].size() > 0 & discovered[i] == 0) { isBinaryGraph = this.bfs(i); if (!isBinaryGraph) break; } } return this.isBinaryGraph; } public boolean bfs(int parent) { Queue<Integer> q = new LinkedList<>(); q.add(parent); while (!q.isEmpty()) { int now = q.poll(); if (discovered[now] == 0) { discovered[now] = Binary[toggle]; } toggle = (discovered[now] == -1 ? 1 : 0); for (int tmp : graph[now]) { if (discovered[tmp] == 0) { q.add(tmp); discovered[tmp] = Binary[toggle]; } else if (discovered[tmp] == discovered[now]) return false; } } return true; } } public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); while (T > 0) { int v = sc.nextInt(); int e = sc.nextInt(); sc.nextLine(); Graph g = new Graph(v); for (int i = 0; i < e; i++) { int a = sc.nextInt(); int b = sc.nextInt(); g.DoubleAdd(a,b); } if (g.solution()) System.out.println("YES"); else System.out.println("NO"); T-=1; } sc.close(); } }

โœ๏ธ Review

  • ๋…ผ๋ฆฌ๋Š” "DFS๋ฅผ ์ด์šฉํ•ด ํ™€์ˆ˜๊ฐœ์˜ ์ •์ ๋ผ๋ฆฌ ์‚ฌ์ดํด์„ ์ด๋ฃจ๋Š” ๊ฒฝ์šฐ ์ด๋ถ„๊ทธ๋ž˜ํ”„๊ฐ€ ๋  ์ˆ˜ ์—†๋‹ค" ์˜€๊ณ , ๋ฐ˜๋ก€๋ฅผ ํ†ตํ•ด ํ™•์ธํ–ˆ์„๋•Œ ์–ผ์ถ” ๋งž๋Š” ๊ฒƒ ๊ฐ™์œผ๋‚˜, ๊ณ„์† ๋Ÿฐํƒ€์ž„ ์—๋Ÿฌ (IndexOutOfBounds) ๊ฐ€ ๋– ์„œ ์ง„์ „์ด ์—†์—ˆ๋‹ค.
  • 10๋ฒˆ ์ด์ƒ์˜ ์—๋Ÿฌ๋กœ ์ •์‹ ์ด ๋‚˜๊ฐ€๋ฒ„๋ฆด ๊ฒƒ ๊ฐ™์•„ BFS๋ฅผ ์ด์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•์œผ๋กœ ๋ฐ”๊ฟ”๋ณด๊ธฐ๋กœ ํ–ˆ๋‹ค.

    • BFS๋ฅผ ์ด์šฉํ•˜๋Š” ๊ฒฝ์šฐ, ๋ฐฉ๋ฌธ ์ˆœ์„œ๋กœ๋Š” ํ•ด๊ฒฐํ•  ์ˆ˜ ์—†์„ ๊ฒƒ ๊ฐ™์•„ ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์„ ๊ณ ์•ˆํ•ด์•ผ ํ–ˆ๋‹ค.
  • DFS, BFS๋ฅผ ํ™•์‹คํ•˜๊ฒŒ ์ดํ•ดํ•  ์ˆ˜ ์žˆ์—ˆ๋˜ ๊ฒƒ ๊ฐ™๋‹ค.
String str = sc.nextLine(); int a = str.charAt(0) - '0'; int b = str.charAt(2) - '0';
  • ์œ„ ๋ฐฉ์‹์œผ๋กœ 1 2 ํ˜•์‹์˜ ์ˆซ์ž๋ฅผ ์ž…๋ ฅ๋ฐ›์œผ๋‹ˆ 10 12 ์™€ ๊ฐ™์€ ๊ฒฝ์šฐ ๋‹น์—ฐํžˆ ํ‹€๋ฆด ์ˆ˜ ๋ฐ–์— ์—†์—ˆ๋‹ค ...

๐Ÿ“• ์ถœ์ฒ˜

https://www.acmicpc.net/problem/1707

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€